//:

import 
	tango.core.Memory,
	tango.stdc.string ,
	tango.core.Thread,
	tango.sys.Common ,
	tango.time.Clock,
	tango.io.Stdout ;

ev_timer[] 	list = [{2}, {1}, {3}, {4}, {3}, {17.6}, {22.5}, {0.3}] ;

void main() {
	ev_loop loop ;
	foreach(int i, ref ev; list){
		assert(ev._id is -1) ;
		ev.setTimeout(&loop, ev._ts) ;
	}
	
	double ts	= ev_timer.now ;
	foreach(int i, ev_timer* ev; loop) {
		assert( ev._id is i);
		Stdout.formatln("{}	{:7}", i, ev._ts - ts );
	}
	
	while( !loop.empty ){
		auto ev	= loop.pop; 
		Stdout.formatln("{:7}", ts - ev._ts  );
	}
	
}

struct ev_loop {
	ev_timer**	p	= null ;
	uint		a , n ;
	
	void Init() {
		
	}
	
	void Reset(){
		if( p !is null ) {
			GC.free(p) ;
		}
		a	= 0 ;
		n	= 0 ;
	}
	
	private int Reserve(uint n){
		if (this.a < n) {
			ev_timer** p;
			uint a = this.a ? this.a * 2 : 8;
			if ( a < n)
				a = n;
			p	= cast(ev_timer**) GC.realloc(this.p, a * size_t.sizeof, GC.BlkAttr.NO_MOVE | GC.BlkAttr.NO_SCAN ) ;
			assert(p !is null);
			if ( p is null)
				return -1;
			this.p = p;
			this.a = a;
		}
		return 0;
	}
	
	private void ShiftUp(uint hole_index, ev_timer* e){
		uint parent = (hole_index - 1) / 2 ;
		while (hole_index && this.p[parent]._ts >  e._ts ) {
			this.p[hole_index]	= this.p[parent] ; 
			this.p[parent]._id	= hole_index ;
			
			hole_index	= parent;
			parent	= (hole_index - 1) / 2;
		}
		this.p[hole_index] = e ;
		e._id	= hole_index ;
	}
	
	private void ShiftDown(uint hole_index, ev_timer* e) {
		uint min_child = 2 * (hole_index + 1);
		while (min_child <= this.n) {
			if( min_child is this.n || this.p[min_child]._ts > this.p[min_child-1]._ts ){
				min_child--;
			}
			if( e._ts <= this.p[min_child]._ts ) {
				break ;
			}
			this.p[hole_index]	= this.p[min_child];
			this.p[min_child]._id	= hole_index ;
			
			hole_index	= min_child ;
			min_child	= 2 * (hole_index + 1) ;
		}
		this.p[hole_index] = e ;
		e._id	= hole_index ;
	}
	
	private int erase(ev_timer* e){
		if (  e._id !is -1 ) {
			-- this.n;
			ev_timer*	last = *( this.p + this.n ) ;
			uint parent = (e._id - 1) / 2;
			/* we replace e with the last element in the heap.  We might need to
			   shift it upward if it is less than its parent, or downward if it is
			   greater than one or both its children. Since the children are known
			   to be less than the parent, it can't need to shift both up and
			   down. */
			if (e._id > 0 && (*(this.p + parent))._ts > last._ts ){
				ShiftUp(e._id, last) ;
			}else{
				ShiftDown(e._id, last) ;
			}
			e._id = -1;
			return 0;
		}
		return -1;
	}
	
	private double timeout(){
		if( this.n is 0 ) {
			return 0 ;
		}
		double _ts	= (*this.p)._ts - ev_timer.now ;
		return _ts ;
	}
	
	bool empty(){
		return this.n is 0 ;
	}
	
	ev_timer* top() {
		if( this.n ) {
			return this.p[0] ;
		}
		return null ;
	}

	ev_timer* pop(){
		if ( this.n ) {
			ev_timer* e = this.p[0] ;
			ShiftDown(0, this.p[ -- this.n] );
			e._id = -1 ;
			return e ;
		}
		return null ;
	}
	
	int push(ev_timer* e) {
		if ( Reserve(this.n + 1) )
			return -1;
		ShiftUp( this.n++, e) ;
		return 0;
	}
	
	
	int opApply (int delegate (ref int , ref ev_timer*) dg) {
		int  i, ret ;
		ev_timer* it;
		for( i =0 ; i <this.n; i++){
			it	= this.p[i] ;
			ret	= dg(i, it) ;
			if( ret !is 0 ){
				return ret ;
			}
		}
		return ret ;
	}
}

struct ev_timer {
	private  {
		double	_ts ;
		int		_id 	= -1 ;
		void function(ev_loop*, void*)	_cb ;
	}
	
	static double now() {
		long ft ;
		version(Win32) {
			GetSystemTimeAsFileTime ( cast(FILETIME*) &ft);
  			return (ft - 116444736000000000) * 1e-7 ;
		} else {
			gettimeofday (&ft, null) ;
		}
	}
	
	bool isTop() {
		return _id is 0 ;
	}
	
	void setTimeout(ev_loop* loop, double ts) {
		if( _id !is -1 ) {
			loop.erase(this) ;
		}
		_ts	= now + ts ;
		loop.push(this) ;
	}
	
	void stop(ev_loop* loop) {
		loop.erase(this) ;
	}
}